/**
 * 
 */
package base.algorithm;

/**
 * 斐波那契数列
 * @author Administrator
 *
 */
public class Fibonacci {
	public static int count = 0;
	public static void commonDo(int num){
		int a[] = new int[40];
		a[0] = 1;
		a[1] = 1;
		for (int j = 2; j < num; j++) {
			a[j] = a[j-1]+a[j-2];
			System.out.print(a[j] + "^");
		}
	}
	
	public static int recursion(int num){
		count++;
		if(num <2)
			return 1;
		return recursion(num - 1)+ recursion(num - 2) ;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		commonDo(20);
		//System.out.println();
		for (int i = 0; i < 20; i++) {
			System.out.print(recursion(i)+ "^");
			System.out.println(i + "^" + count + "^");
			count = 0;
			//System.out.print(recursion(2) + "^");
		}
	
	}

}
